package william.stack;

import java.util.LinkedList;

/**
 * @author ZhangShenao
 * @date 2024/3/13
 * @description <a href="https://leetcode.cn/problems/evaluate-reverse-polish-notation/">...</a>
 */
public class Leetcode150_逆波兰表达式求值 {
    /**
     * 借助栈实现
     * 遍历字符串数组,针对每个字符串进行判断:
     * -如果是数字,则直接将数字入栈
     * -如果是运算符,则从栈顶弹出两个数字,使用运算时进行运算,并将结果压栈
     * <p>
     * 时间复杂度O(N) 需要遍历一次数组
     * 空间复杂度O(N) 需要额外申请一个栈,长度为字符串数组长度
     */
    public int evalRPN(String[] tokens) {
        //边界条件校验
        if (tokens == null || tokens.length < 1) {
            throw new IllegalArgumentException("invalid input!");
        }

        //借助一个栈,保存操作数
        LinkedList<Integer> stack = new LinkedList<>();

        //遍历字符串数组,针对每个字符串进行判断
        for (String token : tokens) {
            if (isOperator(token)) {  //遇到运算符,从栈顶弹出两个数字,使用运算时进行运算,并将结果压栈
                int y = stack.pop();
                int x = stack.pop();
                int result = calc(x, y, token);
                stack.push(result);
            } else { //遇到数字,直接将数字入栈
                stack.push(Integer.parseInt(token));
            }

        }

        //最后返回栈顶元素,即为最终结果
        return stack.pop();
    }

    /**
     * 判断一个字符串是否为运算符
     */
    private boolean isOperator(String token) {
        return ("+".equals(token) || "-".equals(token)
                || "*".equals(token) || "/".equals(token));
    }

    /**
     * 使用运算符进行计算
     */
    private int calc(int x, int y, String operator) {
        if ("+".equals(operator)) {
            return (x + y);
        }
        if ("-".equals(operator)) {
            return (x - y);
        }
        if ("*".equals(operator)) {
            return (x * y);
        }
        return (x / y);
    }
}
